//
// Created by Administrator on 2021/11/4.
// May Saint Diana bless you!
//
#include <vector>
#include <iostream>
#include <algorithm>


using namespace std;

class Solution {
public:
    // 暴力模拟
    vector<int> processQueries(vector<int> &queries, int m) {
        vector<int> v(m, 0);
        for (int i = 0; i < m; ++i) {
            v[i] = i + 1;
        }
        vector<int> ans;
        for (int &querie: queries) {
            auto pos = find(v.begin(), v.end(), querie);
            ans.push_back(pos - v.begin());
            v.erase(pos);
            v.insert(v.begin(), querie);
        }
        return ans;
    }

    // 只标记每个数字的index 复杂度还是m*n
    vector<int> processQueries2(vector<int> &queries, int m) {
        // 元素和位置的映射
        vector<int>posMap(m + 1, 0);
        for (int i = 1; i < m+1; ++i) {
            posMap[i] = i-1;  // 1在0处  2在1处。。
        }
        vector<int>ans;
        for(const int &x:queries){
            ans.push_back(posMap[x]);
            int pos = posMap[x];
            for (int i = 1; i < posMap.size(); ++i) {
                if (posMap[i]<pos)
                    ++ posMap[i];
            }
            posMap[x] = 0;
        }
        return ans;
    }
};

int main() {
    vector<int> queries{3, 1, 2, 1};
    Solution solution;
    vector<int> ans = solution.processQueries2(queries, 5);
    for (const int &x: ans) cout << x << endl;
    return 0;
}
